package leetcode.动态规划.零一背包;

public class Leetcode474 {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            int sum0 = 0;
            int sum1 = 0;
            for (int j = 0; j < s.length(); j++) {
                if(s.charAt(j)=='0'){
                    sum0++;
                }else if(s.charAt(j)=='1'){
                    sum1++;
                }
            }
            for(int j = m;j>=sum0;j--){
                for(int k = n;k>=sum1;k--){
                    dp[j][k] = Math.max(dp[j][k],dp[j-sum0][k-sum1]+1);
                }
            }
        }
        return dp[m][n];
    }
}
